package newcoder_exp.ctrip;
import java.util.*;
import java.util.stream.Collectors;

import org.junit.Test;

public class ctrip0 {


   /*
    1. 一辆车，开始时间为x，结束时间为y，订单金额为z，维度都是n(n个订单)，求最大收益
    任何时间段(x[i] ~ y[i]中只有一个在做订单)
    */
    class Node {
        int start;
        int end;
        int cost;
    }
    // public int maxProfit(int[] x, int[] y, int[] z) {

    // }

    /* 
    2. 周游世界问题
    有n个景点，有0 ~ n-1 的编号
    游客到达每个景点有各自的得分，即mark[i] = ?
    游客初始时在0号景点，并获取0号景点得分mark[0]
    游客还拥有步数卡m张【不一定步数相同】，存储在step数组中, 游客可以消耗一张步数卡到达当前编号 + 步数的景点
    求最大得分

    如：mark = {1, 2, 3, 4}, step = {1, 2}
    则最大得分为8， 路径为 1 -> 3(1 + 2) -> 4(3 + 1)
*/
    public int maxPoints(int[] mark, int[] step) {
        Set<Integer> set = Arrays.stream(step).boxed().collect(Collectors.toSet());
        return dfs(mark, set, 0, 0, new LinkedList<>());
    }

    public int dfs(int[] mark, Set<Integer> step, int cur, int points, List<Integer> path) {
        if (cur >= mark.length) {
            //当前已经超过了所能游览的范围，或者没有步数卡，停止递归
            System.out.println(path + ": " + points);
            return points;
        }
        if (step.isEmpty()) {
            points += mark[cur];
            path.add(cur);
            System.out.println(path + ": " + points);
            path.remove(path.size() - 1);
            return points;
        }

        int res = 0;
        points += mark[cur];
        path.add(cur);
        //根据当前持有的步数卡选择一条路径
        Set<Integer> set = new HashSet<>(step);
        for (int s: step) {
            set.remove(s);
            int c = dfs(mark, set, cur + s, points, path);
            if (c > res) {
                res = c;
            }
            set.add(s);
        }
        path.remove(path.size() - 1);
        return res;
    }

    @Test
    public void test() {
        int[] mark = {1, 2, 3, 4};
        int[] stemp = {1, 2};
        int res = maxPoints(mark, stemp);
        System.out.println(res);
    }

    public int rand3() {
        return (int)(Math.random() * 3) + 1;
    }
    int rand7() {
        while (true) {
         int s = (rand3() - 1) * 3, sum = s + rand3() - 1;
         if (sum >= 7) {
             continue;
         } else {
             return sum + 1;
         }
     }
    }
    @Test
    public void test3() {
        int[] res = new int[7];
        for (int i = 0; i < 100000; i++) {
            res[rand7() - 1]++;
        }
        System.out.println(Arrays.toString(res));
    }
}

